#pragma once

#include <atomic>

namespace hsby {
template<typename T>
class NoLockQueue {
private:
    struct Node {
        Node(const T& val) : value(val), next(nullptr) {}
        T value;
        std::atomic<Node*> next;
    };

public:
    NoLockQueue(){
        head_ = tail_ = new Node(T());
    }
    ~NoLockQueue() {
        Node* p = head_;
        while (p) {
            Node* next = p->next;
            delete p;
            p = next;
        }
    }

    void Push(const T& v) {
        Node* node = new Node(v);
        Node* old_tail = nullptr;
        Node* nullnode = nullptr;
        do {
            old_tail = tail_;
        }while(!old_tail->next.compare_exchange_weak(nullnode, node));
        tail_.compare_exchange_weak(old_tail, node);
    }

    T Pull() {
        Node* old_head = head_;
        T v;
        do {
            Node* next = old_head->next.load();
            if (next) {
                v = next->value;
            }else {
                return T();
            }
        }while(!head_.compare_exchange_weak(old_head, old_head->next));
        delete old_head;
        return v;
    }

private:
    std::atomic<Node*> head_;
    std::atomic<Node*> tail_;
};
}//namespace hsby